{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Monotone Increasing Digits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: monotoneIncreasingDigits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #单调递增的数字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>当且仅当每个相邻位数上的数字&nbsp;<code>x</code>&nbsp;和&nbsp;<code>y</code>&nbsp;满足&nbsp;<code>x &lt;= y</code>&nbsp;时，我们称这个整数是<strong>单调递增</strong>的。</p>\n",
    "\n",
    "<p>给定一个整数 <code>n</code> ，返回 <em>小于或等于 <code>n</code> 的最大数字，且数字呈 <strong>单调递增</strong></em> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 10\n",
    "<strong>输出:</strong> 9\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 1234\n",
    "<strong>输出:</strong> 1234\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 332\n",
    "<strong>输出:</strong> 299\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= n &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [monotone-increasing-digits](https://leetcode.cn/problems/monotone-increasing-digits/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [monotone-increasing-digits](https://leetcode.cn/problems/monotone-increasing-digits/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['10', '1234', '332']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        s = [int(i) for i in str(n)]\n",
    "        for i in range(len(s)-1,0,-1):\n",
    "            if s[i]<s[i-1]:\n",
    "                for j in range(i,len(s)):\n",
    "                    s[j]=9\n",
    "                s[i-1]-=1\n",
    "\n",
    "        return int(\"\".join([str(i) for i in s]))\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        number=[]\n",
    "        while n>0:\n",
    "            if len(number)>0 and n%10>number[-1]:\n",
    "                number=[9 for _ in range(len(number))]\n",
    "                number.append(n%10-1)\n",
    "            else:\n",
    "                number.append(n%10)\n",
    "            n=n//10\n",
    "\n",
    "        # print(number)\n",
    "\n",
    "        return sum([10**i*number[i] for i in range(len(number))])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        strnum = str(n)\n",
    "        flag = len(strnum)\n",
    "\n",
    "        for i in range(len(strnum) - 1, 0, -1):\n",
    "            if strnum[i - 1] > strnum[i]:\n",
    "                flag = i \n",
    "                strnum = strnum[:i-1] + str(int(strnum[i - 1]) - 1) + strnum[i:]\n",
    "\n",
    "        for i in range(flag, len(strnum)):\n",
    "            strnum  = strnum[:i] + '9' + strnum[i+1:]\n",
    "        return int(strnum)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        digits = list(str(n))\n",
    "    \n",
    "        # 从右向左遍历\n",
    "        for i in range(len(digits)-1, 0, -1):\n",
    "            if digits[i] < digits[i-1]:\n",
    "                digits[i-1] = str(int(digits[i-1]) - 1)\n",
    "                for j in range(i, len(digits)):\n",
    "                    digits[j] = '9'\n",
    "                    \n",
    "        return int(''.join(digits))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        a = list(str(n))\n",
    "        for i in range(len(a)-1,0,-1):\n",
    "            if int(a[i]) < int(a[i-1]):\n",
    "                a[i-1] = str(int(a[i-1]) - 1)\n",
    "                a[i:] = '9' * (len(a) - i)  #python不需要设置flag值，直接按长度给9就好了\n",
    "        return int(\"\".join(a)) \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, N: int) -> int:\n",
    "        strNum = str(N)\n",
    "        for i in range(len(strNum) - 1, 0, -1):\n",
    "            if strNum[i - 1] > strNum[i]:\n",
    "                strNum = strNum[:i - 1] + str(int(strNum[i - 1]) - 1) + '9' * (len(strNum) - i)\n",
    "        return int(strNum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\" \n",
    " 2023-10-07\n",
    "    https://leetcode.cn/problems/monotone-increasing-digits/solutions/521966/jian-dan-tan-xin-shou-ba-shou-jiao-xue-k-a0mp/\n",
    "    ## [情况 1]\n",
    "    num = 1 2 3 4 2\n",
    "    res = 1 2 3 3 9\n",
    "\n",
    "    从数字的左边开始遍历，找到第一个下降的位置，即 num[i] > num[i+1] (即上面的例子中为 4 所处的位置);\n",
    "    将该位置的数值减 1, 后面的值全部变为 9: 4 --> 3, 2 --> 9\n",
    "\n",
    "    ## [情况 2]\n",
    "    num = 1 6 6 6 2\n",
    "    res = 1 5 6 6 9\n",
    "\n",
    "    此时在找到第一个下降位置之后 (例子中的倒数第二个位置 6),还需要向前遍历,找到同值区间的左端点(正数第 2 个位置),即在 index [1, 3] 上的值相同,全部为 6. 将左端点的 6 - 1, 区间右端点的后面全部变为 9,即 index=4 后面全部变为 9\n",
    " \"\"\"\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        num = list(str(n))\n",
    "        ## step1: 找出第一个出现下降的位置\n",
    "        idx_right = len(num) - 1  ## 默认设置为最后一个 index\n",
    "        for i in range(len(num) - 1):\n",
    "            if num[i] > num[i+1]:\n",
    "                idx_right = i \n",
    "                break\n",
    "\n",
    "        ## step2: 找出同值区间的左端点(即与 idx_right 位置处的值相同的区间的左端点)\n",
    "        ## 左边的数组为升序\n",
    "        idx_left = idx_right  ## NOTE idx left 默认为 idx right，即当 idx right 的值只出现一次\n",
    "        for i in range(idx_right-1, -1, -1):\n",
    "            if num[i] == num[i+1]:\n",
    "                idx_left = i\n",
    "            elif num[i] < num[i+1]:  ## 特例: 332\n",
    "                break\n",
    "\n",
    "        if idx_right == len(num) - 1:\n",
    "            return int(\"\".join(num))\n",
    "        \n",
    "        ## step3: idx_left 位置处减 1, (idx_left, n) 后面全部变为 9\n",
    "        num[idx_left] = str(int(num[idx_left]) - 1)\n",
    "        for i in range(idx_left+1, len(num)):\n",
    "            num[i] = \"9\"\n",
    "\n",
    "        result = int(\"\".join(num))\n",
    "        return result\n",
    "\n",
    "\n",
    "\n",
    "# n = 1234\n",
    "# r = Solution().monotoneIncreasingDigits(n)  ## answer = 1234\n",
    "# print(r)\n",
    "\n",
    "# n = 332\n",
    "# r = Solution().monotoneIncreasingDigits(n)  ## answer = 299\n",
    "# print(r)\n",
    "\n",
    "# n = 120\n",
    "# r = Solution().monotoneIncreasingDigits(n)  ## answer = 119\n",
    "# print(r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        strNum = list(str(n))\n",
    "        for i in range(len(strNum) - 1, 0, -1):\n",
    "            if strNum[i - 1] > strNum[i]:\n",
    "                strNum[i - 1] = str(int(strNum[i - 1]) - 1)\n",
    "                for j in range(i, len(strNum)):\n",
    "                    strNum[j] = '9'\n",
    "        return int(''.join(strNum))\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "\n",
    "        s = list(str(n))\n",
    "\n",
    "        for i in range(len(s) - 1, 0, -1):\n",
    "            if int(s[i]) < int(s[i - 1]):\n",
    "                s[i - 1] = str(int(s[i - 1]) - 1)\n",
    "                s[i:] = '9' * (len(s) - i)\n",
    "\n",
    "        return int(\"\".join(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        digits = list(str(n))\n",
    "        length = len(digits)\n",
    "        i = length - 2\n",
    "\n",
    "        while i >= 0:\n",
    "            if digits[i] > digits[i+1]:\n",
    "                digits[i] = str(int(digits[i]) - 1)\n",
    "                digits[i+1:] = ['9'] * (length - i - 1)\n",
    "            i -= 1\n",
    "\n",
    "        return int(''.join(digits))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        digits = [int(i) for i in list(str(n))]\n",
    "        if len(digits) == 1: return n\n",
    "\n",
    "        for i in range(len(digits)-1, 0, -1):\n",
    "            if digits[i] < digits[i - 1]:\n",
    "                digits[i:] = [9] * (len(digits) - i)\n",
    "                digits[i - 1] -= 1\n",
    "\n",
    "        res = 0\n",
    "        for num in digits: res = res * 10 + num\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        lista = list(str(n))\n",
    "        length = len(lista)\n",
    "        for i in range(length - 1, 0, -1):\n",
    "            if int(lista[i - 1]) > int(lista[i]):\n",
    "                lista[i - 1] = str(int(lista[i - 1]) - 1)\n",
    "                lista[i:] = '9' * (length - i)\n",
    "        return int(''.join(lista))\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, N: int) -> int:\n",
    "        s = list(str(N))\n",
    "        n = len(s)\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if int(s[i]) > int(s[i + 1]):\n",
    "                s[i + 1:] = '9' * (n - 1 - i)\n",
    "                s[i] = str(int(s[i]) - 1)\n",
    "        return int(''.join(s)) \n",
    "       \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "      \n",
    "        list1 = list(map(int, str(n)))\n",
    "        flag = 0\n",
    "        for i in range(len(list1) - 1, 0, -1):\n",
    "            # 如果当前字符比前一个字符小，说明需要修改前一个字符\n",
    "            if list1[i - 1] > list1[i]:\n",
    "                flag = i\n",
    "                list1[flag-1] -= 1\n",
    "\n",
    "        if flag != 0:\n",
    "           \n",
    "            for i in range(flag, len(list1)):\n",
    "                list1[i] = 9\n",
    "        return int(\"\".join(map(str,list1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        s=list(str(n))\n",
    "        i=1\n",
    "        while i<len(s) and s[i-1]<=s[i]:\n",
    "            i+=1\n",
    "        if i<len(s):\n",
    "            while i>0 and s[i-1]>s[i]:\n",
    "               s[i-1]=str(int(s[i-1])-1)\n",
    "               i-=1\n",
    "        for j in range(i+1,len(s)):\n",
    "            s[j]='9'\n",
    "        return int(\"\".join(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        nums = list(str(n))\n",
    "        nums = list(map(int, nums))\n",
    "        for i in range(len(nums)-1, 0, -1):\n",
    "            if nums[i-1] > nums[i]:\n",
    "                nums[i-1] -= 1\n",
    "                for j in range(i, len(nums)):\n",
    "                    nums[j] = 9\n",
    "        nums = list(map(str, nums))\n",
    "        return int(\"\".join(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        arr = []\n",
    "        while n > 0:\n",
    "            arr.append(n % 10)\n",
    "            n = n // 10\n",
    "        for i in range(1, len(arr)):\n",
    "            if arr[i] > arr[i - 1]:\n",
    "                for j in range(0, i):\n",
    "                    arr[j] = 9\n",
    "                arr[i] -= 1\n",
    "        res = 0\n",
    "        for i in range(len(arr) - 1, -1, -1):\n",
    "            res = res * 10 + arr[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        s = list(str(n))\n",
    "        s_len = len(s)\n",
    "        for i in range(len(s)-1):\n",
    "            if s[i] > s[i+1]:\n",
    "                j = s[:i+1].index(s[i])\n",
    "                s[j] = str(int(s[j])-1)\n",
    "                s[j+1:] = ['9'] * (s_len-j-1)\n",
    "        print(s)\n",
    "        return int(\"\".join(s))\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        s = list(str(n))\n",
    "        pos = 1\n",
    "        length = len(s)\n",
    "        while pos < length and s[pos - 1] <= s[pos]: pos += 1\n",
    "        if pos < length:\n",
    "            while pos > 0 and s[pos - 1] > s[pos]:\n",
    "                s[pos - 1] = str(int(s[pos - 1]) - 1)\n",
    "                pos -= 1\n",
    "            for i in range(pos+1, length):\n",
    "                s[i] = '9'\n",
    "        return int(''.join(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        strNum=list(str(n))\n",
    "        for i in range(len(strNum)-1,0,-1):\n",
    "            if strNum[i-1]>strNum[i]:\n",
    "                strNum[i-1]=str(int(strNum[i-1])-1)\n",
    "                for j in range(i,len(strNum)):\n",
    "                    strNum[j]='9'\n",
    "        return int(''.join(strNum))\n",
    "\n",
    "        #332:329,299"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        \"\"\"贪心-版本四\"\"\"\n",
    "        strNum = str(n)\n",
    "\n",
    "        for i in range(len(strNum)-1, 0, -1):\n",
    "            if strNum[i-1] > strNum[i]:\n",
    "                strNum = strNum[:i-1] + str(int(strNum[i-1])-1) + '9' * (len(strNum)-i)\n",
    "\n",
    "        return int(strNum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        sn = str(n)\n",
    "        flag = len(sn)\n",
    "        for i in range(len(sn) - 1, 0, -1):\n",
    "            if sn[i] < sn[i - 1]:\n",
    "                flag = i\n",
    "                sn = sn[:i - 1] + str(int(sn[i - 1]) - 1) + sn[i:]\n",
    "        for i in range(flag, len(sn)):\n",
    "            sn = sn[:i] + '9' + sn[i + 1:]\n",
    "        return int(sn)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        digits = [int(i) for i in list(str(n))]\n",
    "        if len(digits) == 1: return n\n",
    "\n",
    "        for i in range(len(digits)-1, 0, -1):\n",
    "            if digits[i] < digits[i - 1]:\n",
    "                digits[i:] = [9] * (len(digits) - i)\n",
    "                digits[i - 1] -= 1\n",
    "\n",
    "        res = 0\n",
    "        for num in digits: res = res * 10 + num\n",
    "        return res\n",
    "\n",
    "# 作者：MatthewWang\n",
    "# 链接：https://leetcode.cn/problems/monotone-increasing-digits/solutions/1530717/jian-dan-ming-liao-de-by-matthewow-m-3rrr/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        digits = list(map(int, list(str(n))))\n",
    "        l = len(digits)\n",
    "        ans = []\n",
    "        for i in range(len(digits)):\n",
    "            if not ans:\n",
    "                ans.append(digits[i])\n",
    "            else:\n",
    "                if digits[i] >= ans[-1]:\n",
    "                    ans.append(digits[i])\n",
    "                else:\n",
    "                    k = ans.pop() - 1\n",
    "                    while ans and k < ans[-1]:\n",
    "                        k = ans.pop() - 1\n",
    "                    ans.append(k)\n",
    "                    break\n",
    "        ans = \"\".join([str(i) for i in ans])\n",
    "        ans += (l - len(ans)) * \"9\"\n",
    "        \n",
    "        return int(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        strNum = list(str(n))\n",
    "\n",
    "        for i in range(len(strNum) - 1, 0, -1):\n",
    "            if strNum[i - 1] > strNum[i]:\n",
    "                strNum[i - 1] = str(int(strNum[i - 1]) - 1)\n",
    "                strNum[i:] = '9' * (len(strNum) - i)\n",
    "            \n",
    "        return int(''.join(strNum))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        m = len(str(n))\n",
    "        if m == 1:\n",
    "            return n\n",
    "        num = [0] * m\n",
    "        i = 0\n",
    "        j = 0\n",
    "        while True:\n",
    "            num[i] = (n % (10 ** (m - i))) // (10 ** (m - i - 1))\n",
    "            if i > 0 and num[i] > num[i - 1]:\n",
    "                j = i\n",
    "            elif i > 0 and num[i] < num[i - 1]:\n",
    "                num[j] -= 1\n",
    "                for k in range(j + 1, m):\n",
    "                    num[k] = 9\n",
    "                break\n",
    "            i += 1\n",
    "            if i == m:\n",
    "                return n\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            ans += num[i] * (10 ** (m - i - 1))\n",
    "        return ans        \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        for i in range(len(s)-2, -1, -1):\n",
    "            if int(s[i]) > int(s[i+1]):\n",
    "                s = s[:i] + str(int(s[i]) - 1) + '9' * (len(s) - i - 1)\n",
    "        return int(s)\n",
    "\n",
    "\n",
    "\n",
    "  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        n = [int(x) for x in str(n)]\n",
    "        i = 0 \n",
    "        flag = False\n",
    "        while i < len(n) - 1:\n",
    "            while i >= 0 and n[i+1] < n[i]:\n",
    "                flag = True\n",
    "                n[i] = n[i] - 1\n",
    "                i -= 1\n",
    "            i += 1\n",
    "            if flag:\n",
    "                break  \n",
    "        i += 1\n",
    "        for idx in range(i, len(n)):\n",
    "            n[idx] = 9\n",
    "\n",
    "        return int(''.join(map(str, n)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        n_s = str(n)\n",
    "        ls = [int(d) for d in n_s]\n",
    "\n",
    "        digits = len(n_s)\n",
    "        for i in range(1, digits):\n",
    "            if ls[i] < ls[i - 1]:\n",
    "                for j in range(i, digits):\n",
    "                    ls[j] = 9\n",
    "                k = i - 1\n",
    "                while k - 1 >= 0:\n",
    "                    if ls[k] > ls[k - 1]:\n",
    "                        ls[k] -= 1\n",
    "                        break\n",
    "                    ls[k] = 9\n",
    "                    k = k - 1\n",
    "                if k == 0:\n",
    "                    ls[0] -= 1\n",
    "                    if ls[0] == 0:\n",
    "                        del ls[0]\n",
    "                break\n",
    "        res = 0\n",
    "        for d in ls:\n",
    "            res = res * 10 + d\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        n=[int(i) for i in list(str(n))]\n",
    "        flag=len(n)\n",
    "        for i in range(len(n)-1,0,-1):\n",
    "            if n[i]<n[i-1]:\n",
    "                flag=i \n",
    "                n[i-1]-=1\n",
    "        for i in range(flag,len(n)):\n",
    "            n[i]=9\n",
    "        print(n)\n",
    "        n=[str(i) for i in n]\n",
    "        n=''.join(n)\n",
    "        return int(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        strNum = list(str(n))\n",
    "        for i in range(1,len(strNum))[::-1]:\n",
    "            if strNum[i] < strNum[i-1]:\n",
    "                strNum[i-1] = str(int(strNum[i-1]) - 1)\n",
    "                for j in range(i,len(strNum)):\n",
    "                    strNum[j] = '9'\n",
    "        return int(''.join(strNum))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        if n<10:\n",
    "            return n\n",
    "        digits=[int(i) for i in list(str(n))]\n",
    "        res=0\n",
    "        for i in range(len(digits)-1,0,-1):\n",
    "            if digits[i]<digits[i-1]:\n",
    "                digits[i:]=[9]*(len(digits)-i)\n",
    "                digits[i-1]-=1\n",
    "        for x in digits:\n",
    "            res=res*10+x\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        strnum = str(n)\n",
    "\n",
    "        for i in range(len(strnum)-1, 0, -1):\n",
    "            if strnum[i-1] > strnum[i]:\n",
    "                strnum = strnum[: i-1]+ str(int(strnum[i-1])-1) + '9' * (len(strnum)-i)\n",
    "        return int(''.join(strnum))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        list_num = []\n",
    "        while n:\n",
    "            mode = n % 10\n",
    "            list_num.append(mode)\n",
    "            n //= 10\n",
    "\n",
    "        for i in range(len(list_num)-1):\n",
    "            this_num = list_num[i]\n",
    "            if this_num < list_num[i+1]:\n",
    "                # list_num[i] = 9\n",
    "                list_num[i+1] -= 1\n",
    "                for j in range(i+1):\n",
    "                    list_num[j] = 9\n",
    "        # print(list_num)\n",
    "        ans = 0\n",
    "        for i in range(len(list_num)):\n",
    "            ans += list_num[i] * 10 ** i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "\n",
    "        nums = list(map(int, str(n)))\n",
    "\n",
    "        flag = len(nums)\n",
    "\n",
    "        for i in range(len(nums)-1, 0, -1):\n",
    "            if nums[i] < nums[i-1]:\n",
    "                nums[i-1] -= 1\n",
    "                flag = i\n",
    "\n",
    "        for i in range(flag, len(nums)):\n",
    "            nums[i] = 9\n",
    "\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            res += nums[i]*10**(len(nums)-i-1)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        snum = str(n)\n",
    "        res  = []\n",
    "        index = 0\n",
    "        res.append(snum[index])\n",
    "        while res[index] == snum[index] and len(res) < len(snum):\n",
    "            if index+1 < len(snum) and res[index] > snum[index+1]:\n",
    "                res[index] = str(int(snum[index])-1)\n",
    "            while index > 0 and res[index] < res[index-1]:\n",
    "                res[index-1] =  res[index]\n",
    "                index -= 1\n",
    "            if res[index] == snum[index]:\n",
    "                index += 1\n",
    "                res.append(snum[index])\n",
    "        res = res[:index+1]\n",
    "        res.append('9'*(len(snum)-index-1))\n",
    "        return int(''.join(res)) \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        n = list(str(n))\n",
    "        for i in range(len(n)-1, 0, -1):\n",
    "            if n[i-1] > n[i]:\n",
    "                n[i-1] = str(int(n[i-1]) - 1)\n",
    "                for x in range(i, len(n)):\n",
    "                    n[x] = '9'\n",
    "        return int(''.join(n))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        s = list(str(n))\n",
    "        for i in range(len(s) - 1, 0, -1):\n",
    "            if s[i - 1] > s[i]:\n",
    "                s[i - 1] = str(int(s[i - 1]) - 1)\n",
    "                s[i:] = '9' * (len(s) - i)\n",
    "        return int(''.join(s))\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        remainder = n\n",
    "        digits = []\n",
    "        while remainder:\n",
    "            digits = [remainder%10]+digits\n",
    "            remainder=remainder//10\n",
    "        # print(digits)\n",
    "        flag = True\n",
    "        for i in range(len(digits)-1):\n",
    "            if digits[i]>digits[i+1]:\n",
    "                flag = False\n",
    "                break\n",
    "        \n",
    "        if not flag:\n",
    "            while i>0 and digits[i]==digits[i-1]:\n",
    "                i-=1\n",
    "            if digits[i]==0:\n",
    "                j = i\n",
    "                while j>=0:\n",
    "                    if digits[j]==0:\n",
    "                        digits[j]=9\n",
    "                    else:\n",
    "                        digits[j]=digits[j]-1\n",
    "                        break\n",
    "                    j-=1\n",
    "            else:\n",
    "                digits[i]-=1\n",
    "            for j in range(i+1,len(digits)):\n",
    "                digits[j]=9\n",
    "            rs = 0\n",
    "            for i in range(len(digits)):\n",
    "                if digits[i]!=0:\n",
    "                    rs+=digits[i]*(10**(len(digits)-i-1))\n",
    "            return rs\n",
    "        else:\n",
    "            return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        n = list(str(n))\n",
    "        pos = len(n)\n",
    "        for i in range(len(n) - 1, 0, -1):\n",
    "            if n[i - 1] > n[i]:\n",
    "                pos = i\n",
    "                n[i - 1] = str(int(n[i - 1]) - 1)\n",
    "        for i in range(pos, len(n)):\n",
    "            n[i] = '9'\n",
    "        return int(''.join(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        temp = []\n",
    "        while n >= 1:\n",
    "            n, number = n // 10 ,n % 10\n",
    "            temp.append(number)\n",
    "        for i in range(len(temp)-1):\n",
    "            if temp[i] < temp[i+1]:\n",
    "                temp[i+1] -= 1\n",
    "                # temp[i] = 9 \n",
    "                # 会导致之前没有修正的位置不是9，用一个开关符号来记录当前的i，之前的位置全部更换为9\n",
    "                for j in range(i+1):\n",
    "                    temp[j] = 9\n",
    "        # 看题，没有说新生成的数字一定要比原来的数字小\n",
    "        ans = 0\n",
    "        for i in range(len(temp)):\n",
    "            ans += 10 ** i * temp[i]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        if n<10:\n",
    "            return n\n",
    "        digits=[int(i) for i in list(str(n))]\n",
    "        for i in range(len(digits)-1,0,-1):\n",
    "            if digits[i]<digits[i-1]:\n",
    "                digits[i:]=[9]*(len(digits)-i)\n",
    "                digits[i-1]-=1\n",
    "        res=0\n",
    "        for x in digits:\n",
    "            res=res*10+x\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        if n <= 9 :\n",
    "            return n\n",
    "        n = [i for i in str(n)]\n",
    "        if len(n) <= 1 :\n",
    "            return int(n)\n",
    "        for i in range(len(n)-1,0,-1):\n",
    "            if i-1 >= 0 :\n",
    "                if int(n[i-1]) > int(n[i]): #前一个大于当前这个\n",
    "                    n[i-1]=str(int(n[i-1])-1)\n",
    "                    n[i:] = (len(n)-i)* ['9']\n",
    "        return int(''.join(n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        nums = list(str(n))\n",
    "        start = len(nums)\n",
    "\n",
    "        for i in range(len(nums)-1, 0, -1): # [len-1, 0)\n",
    "            if nums[i] < nums[i-1]:\n",
    "                nums[i-1] = str(int(nums[i-1])-1)\n",
    "                start = i\n",
    "        for i in range(start, len(nums)):\n",
    "            nums[i] = '9'\n",
    "        return int(''.join(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        string_num = list(str(n))\n",
    "        string_num = [int(x) for x in string_num]\n",
    "        flag_index = float(\"INF\")\n",
    "        i = len(string_num) - 1\n",
    "        while i > 0:\n",
    "            if string_num[i-1] > string_num[i]:\n",
    "                string_num[i] = 9\n",
    "                flag_index = i\n",
    "                string_num[i-1] -= 1\n",
    "            i -= 1\n",
    "        str_list = []\n",
    "        for i in range(len(string_num)):\n",
    "            if i >= flag_index:\n",
    "                str_list.append(\"9\")\n",
    "            else:\n",
    "                str_list.append(str(string_num[i]))\n",
    "        return int(\"\".join(str_list))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        numberList = [int(i) for i in str(n)]\n",
    "        for i in range(len(numberList)-1,0,-1):\n",
    "            if numberList[i] < numberList[i-1]:\n",
    "                numberList[i:] = [9]*len(numberList[i:])\n",
    "                numberList[i-1] -= 1\n",
    "        count = 0\n",
    "        j = 1\n",
    "        for i in range(len(numberList)-1,-1,-1):\n",
    "            count += numberList[i]*j\n",
    "            j = j*10\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        n = list(str(n))\n",
    "        length = len(n)\n",
    "\n",
    "        for i in range(length-1, 0, -1):\n",
    "            if n[i] < n[i-1]:\n",
    "                n[i-1] = str(int(n[i-1])-1)\n",
    "                for j in range(i, length):\n",
    "                    n[j] = '9'\n",
    "        \n",
    "        return int(''.join(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        s = list(str(n))\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            s[i] = int(s[i])\n",
    "        flag = inf\n",
    "        for i in range(n-1, 0, -1):\n",
    "            if s[i] < s[i-1]: \n",
    "                s[i] = 9\n",
    "                flag = i\n",
    "                s[i-1] -= 1\n",
    "        ans = 0\n",
    "        if flag < n:\n",
    "            for i in range(flag,n):\n",
    "                s[i] = 9\n",
    "        for i in s:\n",
    "            ans = 10*ans\n",
    "            ans += i\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        str_num = str(n)\n",
    "        len_num = len(str_num)\n",
    "        res = list(str_num)\n",
    "\n",
    "        for i in range(len_num-1,0,-1):\n",
    "            if res[i]<res[i-1]:\n",
    "                res[i-1]=str(int(res[i-1])-1)\n",
    "                for j in range(i,len_num):\n",
    "                    res[j]='9'\n",
    "\n",
    "        return int(''.join(res))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        strNum = str(n)\n",
    "        flag = len(strNum)\n",
    "        for i in range(len(strNum)-1, 0, -1):\n",
    "            if strNum[i-1] > strNum[i]:\n",
    "                flag = i\n",
    "                strNum = strNum[:i-1] + str(int(strNum[i-1])-1) + strNum[i:]\n",
    "        strNum = strNum[:flag] + '9' * (len(strNum)-flag)\n",
    "        return int(strNum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def split_digits(self, n):\n",
    "        dg = []\n",
    "        while n>0:\n",
    "            dg.append(int(n%10))\n",
    "            n = int(n/10)\n",
    "        return dg\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        digits = self.split_digits(n)\n",
    "        size = len(digits)\n",
    "        result = 0\n",
    "        i = size-1\n",
    "        while (i>0 and digits[i] <= digits[i-1]):\n",
    "            j = i\n",
    "            while (j>0 and digits[j] == digits[j-1]):\n",
    "                j -= 1\n",
    "            if j>0 and digits[j] > digits[j-1]: break\n",
    "            result += digits[i]*10**i\n",
    "            i -= 1\n",
    "        if i == 0:\n",
    "            result += digits[0]\n",
    "        elif i>0 and i<size:\n",
    "            result += digits[i]*10**i - 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        a=list(str(n))\n",
    "        for i in range(len(a)-1,0,-1):\n",
    "            if a[i]<a[i-1]:\n",
    "                a[i-1]=str(int(a[i-1])-1)\n",
    "                for j in range(i,len(a)):\n",
    "                    a[j]=\"9\"\n",
    "        return int(\"\".join(a))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        # # 设置为字符串长度，为了防止第二个for循环在flag没有被赋值的情况下执行\n",
    "        # 字符串不可变 转成列表\n",
    "        n=list(str(n))\n",
    "        flag = len(n)\n",
    "        for i in range(len(n)-1, 0,-1):\n",
    "            if n[i-1] > n[i]:\n",
    "                n[i-1] = str(int(n[i-1]) - 1)\n",
    "                flag = i\n",
    "        for i in range(flag, len(n)):\n",
    "            n[i] = '9'\n",
    "          \n",
    "        return int(''.join(n))\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        a = list(str(n))  # 把整数拆散为单个数字\n",
    "        for i in range(len(a)-1, 0, -1):  # 从后往前遍历。最后取不到索引0，但是下面的 i-1 就可以取到索引0了\n",
    "            if int(a[i-1]) > int(a[i]):  # 前一个数 大于 后一个数\n",
    "                a[i-1] = str(int(a[i-1]) - 1)  # 前一个数 -1\n",
    "                # 索引i 以及i后面的数字全部改为9\n",
    "                a[i:] = \"9\" * (len(a) - i)  # 索引i 以及i后面的数字, 长度为 len(a) - i\n",
    "        return int(\"\".join(a))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, N: int) -> int:\n",
    "        # 将整数转换为字符串\n",
    "        strNum = list(str(N))\n",
    "\n",
    "        # 从右往左遍历字符串\n",
    "        for i in range(len(strNum) - 1, 0, -1):\n",
    "            # 如果当前字符比前一个字符小，说明需要修改前一个字符\n",
    "            if strNum[i - 1] > strNum[i]:\n",
    "                strNum[i - 1] = str(int(strNum[i - 1]) - 1)  # 将前一个字符减1\n",
    "                # 将修改位置后面的字符都设置为9，因为修改前一个字符可能破坏了递增性质\n",
    "                strNum[i:] = '9' * (len(strNum) - i)\n",
    "\n",
    "        # 将列表转换为字符串，并将字符串转换为整数并返回\n",
    "        return int(''.join(strNum))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        nlist = [int(i) for i in str(n)]\n",
    "        for i in range(len(nlist) - 1, 0, -1):\n",
    "            if nlist[i - 1] > nlist[i]:\n",
    "                nlist[i - 1] -= 1\n",
    "                nlist[i] = 9\n",
    "                while i < len(nlist) - 1:\n",
    "                    nlist[i + 1] = 9\n",
    "                    i += 1\n",
    "        strn = [str(i) for i in nlist]\n",
    "        return int(\"\".join(strn))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        strNum = list(str(n))\n",
    "        for i in range(len(strNum)-1,0,-1):\n",
    "            if strNum[i-1]>strNum[i]:\n",
    "                strNum[i-1]=str(int(strNum[i - 1]) - 1) \n",
    "                strNum[i:]='9' * (len(strNum) - i)\n",
    "        return int(''.join(strNum))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        string_n=str(n)\n",
    "        flag=len(string_n)\n",
    "\n",
    "        for i in range(len(string_n)-1,0,-1):\n",
    "            if int(string_n[i])<int(string_n[i-1])  :\n",
    "                flag=i\n",
    "                string_n=string_n[:i-1]+str(int(string_n[i-1])-1)+string_n[i:]\n",
    "\n",
    "        for i in range(flag,len(string_n)):\n",
    "            string_n=string_n[:i]+'9'+string_n[i+1:]\n",
    "\n",
    "        return int(string_n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def int2list(num):\n",
    "    if num == 0:\n",
    "        return [0]\n",
    "    ans = []\n",
    "    while num > 0:\n",
    "        ans.insert(0, num % 10)\n",
    "        num = num // 10\n",
    "    return ans\n",
    "\n",
    "def list2int(arr):\n",
    "    arr = arr[::-1]\n",
    "    ans = 0\n",
    "    while arr:\n",
    "        ans *= 10\n",
    "        ans += arr.pop()\n",
    "    return ans\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        arr = int2list(n)\n",
    "        curMax = arr[0]\n",
    "        # print(arr)\n",
    "        for i in range(len(arr) - 1):\n",
    "            if arr[i] <= arr[i+1]:\n",
    "                continue\n",
    "            else:\n",
    "                arr[i] -= 1\n",
    "                arr[i+1:] = [9] * len(arr[i+1:])\n",
    "                for j in range(i, 0, -1):\n",
    "                    if arr[j] < arr[j-1]:\n",
    "                        arr[j-1] -= 1\n",
    "                        arr[j] = 9               \n",
    "                break\n",
    "        # print(arr)\n",
    "        flag = 0\n",
    "        for i in range(len(arr)-1, -1, -1):\n",
    "            arr[i] -= flag\n",
    "            if arr[i] == 0:\n",
    "                flag = 1\n",
    "                arr[i] = 9\n",
    "        if flag == 1:\n",
    "            return list2int(arr[1:])\n",
    "            \n",
    "        return list2int(arr)\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        s=list(str(n))\n",
    "        flag=0\n",
    "        for i in range(len(s)-1,0,-1):\n",
    "            if s[i]<s[i-1]:\n",
    "                s[i-1]=str(int(s[i-1])-1)\n",
    "                \n",
    "                s[i:]=\"9\"*(len(s)-i)\n",
    "        return int(\"\".join(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        if n < 10:\n",
    "            return n\n",
    "        l = [int(digit) for digit in str(n)]\n",
    "        flag = len(l)\n",
    "        for i in range(len(l) - 1,0,-1):\n",
    "            if l[i] < l[i - 1]:\n",
    "                flag = i\n",
    "                l[i - 1] -= 1\n",
    "        for i in range(flag,len(l)):\n",
    "            l[i] = 9\n",
    "        result = 0\n",
    "        for i in l:\n",
    "            result *= 10\n",
    "            result += i\n",
    "\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        s = list(str(n))\n",
    "        n = len(s)\n",
    "        flag = n\n",
    "        for i in range(n-1, 0, -1):\n",
    "            if s[i] < s[i-1]: \n",
    "                flag = i\n",
    "                s[i-1] = str(int(s[i-1])-1)\n",
    "        s[flag:] = [\"9\"]*(n - flag)\n",
    "        return int(\"\".join(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        strNum = str(n)\n",
    "        flag = len(strNum)\n",
    "        for i in range(len(strNum) - 1, 0, -1):\n",
    "            if strNum[i - 1] > strNum[i]:\n",
    "                flag = i\n",
    "                strNum = strNum[:i - 1] + str(int(strNum[i - 1]) - 1) + strNum[i:]\n",
    "        for i in range(flag, len(strNum)):\n",
    "            strNum = strNum[:i] + \"9\" + strNum[i + 1:]\n",
    "        return int(strNum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def checkNum(self, num):\n",
    "#         max_digit = 10\n",
    "#         while num:\n",
    "#             digit = num % 10\n",
    "#             if max_digit >= digit:\n",
    "#                 max_digit = digit\n",
    "#             else:\n",
    "#                 return False\n",
    "#             num //= 10\n",
    "#         return True\n",
    "\n",
    "#     def monotoneIncreasingDigits(self, N):\n",
    "#         for i in range(N, 0, -1):\n",
    "#             if self.checkNum(i):\n",
    "#                 return i\n",
    "#         return 0\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, N: int) -> int:\n",
    "        # 将整数转换为字符串\n",
    "        strNum = str(N)\n",
    "        # flag用来标记赋值9从哪里开始\n",
    "        # 设置为字符串长度，为了防止第二个for循环在flag没有被赋值的情况下执行\n",
    "        flag = len(strNum)\n",
    "        \n",
    "        # 从右往左遍历字符串\n",
    "        for i in range(len(strNum) - 1, 0, -1):\n",
    "            # 如果当前字符比前一个字符小，说明需要修改前一个字符\n",
    "            if strNum[i - 1] > strNum[i]:\n",
    "                flag = i  # 更新flag的值，记录需要修改的位置\n",
    "                # 将前一个字符减1，以保证递增性质\n",
    "                strNum = strNum[:i - 1] + str(int(strNum[i - 1]) - 1) + strNum[i:]\n",
    "        \n",
    "        # 将flag位置及之后的字符都修改为9，以保证最大的递增数字\n",
    "        for i in range(flag, len(strNum)):\n",
    "            strNum = strNum[:i] + '9' + strNum[i + 1:]\n",
    "        \n",
    "        # 将最终的字符串转换回整数并返回\n",
    "        return int(strNum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        if n < 10:\n",
    "            return n\n",
    "\n",
    "        str_n = str(n)\n",
    "        size = len(str_n)\n",
    "\n",
    "        start = 0\n",
    "        for i in range(1, size):\n",
    "            if str_n[start] <= str_n[i]:\n",
    "                start = i\n",
    "            else:\n",
    "                break\n",
    "\n",
    "\n",
    "        if start == size - 1:\n",
    "            return n\n",
    "        else:\n",
    "            pos = str_n.find(str_n[start])\n",
    "            rest = str_n[:pos] + str(int(str_n[pos]) - 1) + '9' * (size - pos - 1)\n",
    "\n",
    "            return int(rest)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\r\n",
    "        s = list(str(n))\r\n",
    "        m = len(s)\r\n",
    "        for i in range(m-1, 0, -1):\r\n",
    "            if s[i - 1] > s[i]:\r\n",
    "                s[i - 1] = str(int(s[i - 1]) - 1)  # 将前一个字符减1\r\n",
    "                # 将修改位置后面的字符都设置为9，因为修改前一个字符可能破坏了递增性质\r\n",
    "                for j in range(i, len(s)):\r\n",
    "                    s[j] = '9'\r\n",
    "        return int(\"\".join(s))\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "    #     n_s = [int(i) for i in str(n)]\n",
    "    #     if n <= 9:\n",
    "    #         return n\n",
    "    #     res = ''\n",
    "    #     last = 0\n",
    "    #     for i in range(len(n_s)):\n",
    "    #         if i >0 and n_s[i]< n_s[i-1]:\n",
    "    #             res = \"9\" * (len(n_s) - i -1)\n",
    "    #             n_s = n_s[:i+1]\n",
    "    #             break\n",
    "\n",
    "    #     for i in range(len(n_s)-1, -1, -1):\n",
    "    #         n_s[i] = n_s[i] + last\n",
    "    #         if i == 0 and n_s[i] >=1:\n",
    "    #             res += str(n_s[i])\n",
    "    #         elif i>= 1 and n_s[i] >= n_s[i-1]:\n",
    "    #             res += str(n_s[i])\n",
    "    #             last = 0\n",
    "    #         else:\n",
    "    #             if i != 0:\n",
    "    #                 res += \"9\"\n",
    "    #                 last = -1\n",
    "    #     return int(res[::-1])\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        n_s = [int(i) for i in str(n)]\n",
    "        if n <= 9:\n",
    "            return n\n",
    "        flag = len(n_s)\n",
    "        for i in range(len(n_s)-1, 0, -1):\n",
    "            if n_s[i] < n_s[i-1]:\n",
    "                flag = i\n",
    "                n_s[i-1] -= 1\n",
    "        for i in range(len(n_s)):\n",
    "            if i >= flag:\n",
    "                n_s[i] = 9\n",
    "        res = \"\".join([str(i) for i in n_s])\n",
    "        return int(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        s=[0 for i in range(10)]\n",
    "        for i in range(10):\n",
    "            s[i]=int(n/(10**(9-i)))\n",
    "            n=n-s[i]*(10**(9-i))\n",
    "        i=0\n",
    "        j=i+1\n",
    "        while i<len(s)-1 and j<len(s):\n",
    "            if s[j]>s[i]:\n",
    "                i=j\n",
    "                j+=1\n",
    "            elif s[i]==s[j]:\n",
    "                j+=1\n",
    "            else:\n",
    "                s[i]=s[i]-1\n",
    "                i+=1\n",
    "                while i<len(s):\n",
    "                    s[i]=9\n",
    "                    i+=1\n",
    "        ans=0\n",
    "        for i in range(10):\n",
    "            ans+=s[i]*(10**(9-i))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 从后往前遍历，全置为9，因为要返回最大值\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        n_str = list(str(n)) # 转为列表\n",
    "\n",
    "        for i in range(len(n_str)-1, 0, -1):\n",
    "\n",
    "            if n_str[i-1] > n_str[i] :\n",
    "\n",
    "                n_str[i:] = '9' * (len(n_str) - i ) # str 9\n",
    "                n_str[i-1] = str(int(n_str[i-1]) - 1 ) # 相当于是向前借了一位，所以减一\n",
    "\n",
    "        return int(''.join(n_str))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#greedy\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        # 将整数转换为字符串list\n",
    "        strNum = list(str(n))\n",
    "#因为是与 i-1比较，循环结束条件不能等于0，否则就会出现索引《0， 出问题\n",
    "        for i in range(len(strNum)-1, 0, -1):\n",
    "            if strNum[i] < strNum[i-1]:\n",
    "                strNum[i-1] = str(int(strNum[i-1]) -1)\n",
    "                for j in range(i, len(strNum)):\n",
    "                    strNum[j] = '9'\n",
    "        return int(''.join(strNum))\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        n=list(str(n))\n",
    "        # n=n[::-1]\n",
    "        # res=''\n",
    "        for i in range(len(n)-2,-1,-1):\n",
    "            if int(n[i])>int(n[i+1]):\n",
    "                n[i]=str(int(n[i])-1)\n",
    "                for j in range(i+1,len(n)):\n",
    "                    n[j]='9'\n",
    "        return int(''.join(n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        ns = list()\n",
    "        while True:\n",
    "            q = n // 10\n",
    "            p = n - q * 10\n",
    "            n = q\n",
    "            ns.insert(0, p)\n",
    "            if n == 0:\n",
    "                break\n",
    "        \n",
    "        l = len(ns)\n",
    "        for i in range(len(ns) - 1, 0, -1):\n",
    "            if ns[i] < ns[i - 1]:\n",
    "                ns[i] = 9\n",
    "                ns[i - 1] -= 1\n",
    "                l = min(l, i)\n",
    "        for i in range(l, len(ns)):\n",
    "            ns[i] = 9\n",
    "\n",
    "        ret = 0\n",
    "        for i in range(len(ns)):\n",
    "            ret += ns[len(ns) - 1 - i] * (10 ** i)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        temp = s[len(s)-1]\n",
    "        for i in range(len(s)-2, -1, -1):\n",
    "            if s[i] > temp:\n",
    "                s = s[:i]+str(int(s[i])-1)+\"9\"*(len(s)-i-1)\n",
    "            temp = s[i]\n",
    "        return int(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        #将整数转换为字符串\n",
    "        strNum = str(n)\n",
    "        #flag用来标记赋值9从哪里开始\n",
    "        #设置为字符串长度，为了防止第二个for循环在flag没有被赋值的情况下执行\n",
    "        flag = len(strNum)\n",
    "\n",
    "        #从右往左遍历字符串\n",
    "        for i in range(len(strNum) -1, 0, -1):\n",
    "            #如果当前字符比前一个字符小，说明需要修改前一个字符\n",
    "            if strNum[i - 1] > strNum[i]:\n",
    "                flag = i #更新flag的值，记录需要修改的位置\n",
    "                #将前一个字符减1，，以保证递增性质\n",
    "                strNum = strNum[:i-1] + str(int(strNum[i-1]) - 1) + strNum[i:]\n",
    "        \n",
    "        #将flag位置及之后的字符都修改为9，以保证最大的递增数字\n",
    "        for i in range(flag,len(strNum)):\n",
    "            strNum = strNum[:i] + '9' + strNum[i+1:]\n",
    "        #将最终的字符串转换回整数并返回\n",
    "        return int(strNum)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        nums = [int(i) for i in str(n)]             #将数字转化为int列表\n",
    "        k = len(nums) - 1                       \n",
    "        flag = k + 1                                #flag用来记录哪一位不满足条件，即从这一位开始 后面都赋值为9，因为取最大的\n",
    "        while(k > 0):                               #反向遍历该列表\n",
    "            if nums[k] >= nums[k - 1]:              #如果后一位大于等于前一位，满足题目要求 continue\n",
    "                k -= 1\n",
    "                continue\n",
    "            else:                                   #如果后一位小于前一位，那么将前一位减一，并记录当前位置，继续遍历\n",
    "                nums[k - 1] -= 1\n",
    "                flag = k\n",
    "                k -= 1\n",
    "        if flag == len(nums):                       #如果遍历完了发现flag没有变，那就return原数\n",
    "            return n\n",
    "        else:                                       #flag变了，那就按顺序遍历该列表，从flag开始全都赋值为9\n",
    "            for i in range(len(nums)):\n",
    "                if i >= flag:\n",
    "                    nums[i] = 9\n",
    "            if nums[0] == 0:                        #如果首位是0，那就去掉首位\n",
    "                nums = nums[1:]\n",
    "            return int(''.join(map(str, nums)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monotoneIncreasingDigits(self, n: int) -> int:\n",
    "        strNum = list(str(n))\n",
    "\n",
    "        # 从右往左遍历字符串\n",
    "        for i in range(len(strNum) - 1, 0, -1):\n",
    "            # 如果当前字符比前一个字符小，说明需要修改前一个字符\n",
    "            if strNum[i - 1] > strNum[i]:\n",
    "                strNum[i - 1] = str(int(strNum[i - 1]) - 1)  # 将前一个字符减1\n",
    "                # 将修改位置后面的字符都设置为9，因为修改前一个字符可能破坏了递增性质\n",
    "                for j in range(i, len(strNum)):\n",
    "                    strNum[j] = '9'\n",
    "\n",
    "        # 将列表转换为字符串，并将字符串转换为整数并返回\n",
    "        return int(''.join(strNum))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
